package problem5;

//5.最长回文串
//https://leetcode.cn/problems/longest-palindromic-substring/

//中心扩展算法

class Solution2 {
    public String longestPalindrome(String s) {
        int n = s.length();
        int l = 0, r =0, len = 0;
        for(int k = 0; k<n-1; k++) {
            //回文串长度为奇数
            int i = k, j = k;
            while(i>=0 && j <n && s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            }
            i++;j--;
            if(j-i+1 > len) {
                len = j-i+1;
                l = i;
                r = j;
            }
            //回文串长度为偶数
            i = k;j = k+1;
             while(i>=0 && j <n && s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            }
            i++;j--;
             if(j-i+1 > len) {
                len = j-i+1;
                l = i;
                r = j;
            }
        }

        return s.substring(l, r+1);
    }
}